public class Test {
    ListNode bs = null;
    ListNode be = null;
    ListNode as = null;
    ListNode ae = null;


    ListNode cur = pHead;

        while(cur != null) {
        if(cur.val < x) {
            //第一次插入
            if(bs == null) {
                bs = be = cur;
            }else {
                be.next = cur;
                be = cur;
            }

        }else {
            if(as == null) {
                as = ae = cur;
            }else {
                ae.next = cur;
                ae = cur;
            }
        }
        cur = cur.next;

    }

             if(bs == null) {
        return as;
    }

    be.next = as;

            if(as != null) {
        ae.next = null;
    }


             return bs;



    public boolean chkPalindrome(ListNode A) {
        // write code here

        if(A == null) {
            return false;
        }

        if(A.next == null) {
            return true;
        }

        ListNode slow = A;
        ListNode fast = A;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        while(A != slow ) {
            if(A.val == slow.val) {
                A = A.next;
                slow = slow.next;

                //判断偶数情况
                if(A.next == slow) {
                    return true;
                }
            }else {
                return false;
            }
        }
        return true;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int lenA = 0;
        ListNode curA = headA;
        while(curA != null) {
            lenA++;
            curA = curA.next;
        }


        int lenB = 0;
        ListNode curB = headB;
        while(curB != null) {
            lenB++;
            curB = curB.next;
        }

        int len = lenA - lenB;
        ListNode pl = headA;
        ListNode ps = headB;

        if(len < 0) {
            len = lenB - lenA;
            pl = headB;
            ps = headA;
        }

        while(len != 0) {
            pl = pl.next;
            len--;
        }

        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null) {
            return null;
        }
        return pl;
    }

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast !=null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                while(head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return slow;
            }
        }

        return null;



        public boolean hasCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;

            while(fast !=null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow) {
                    return true;
                }
            }

            return false;

        }
    }
}
